fun main() {
    val array= arrayOf(-4,2,10,9,8,7,6)
    sort(array,0,array.size-1)
    println(array.asList())
    print(array[2])
}
fun sort(array: Array<Int>, start:Int, end:Int) {
    if (start>=end){
        return
    }
    val middle = getMiddle(array, start, end)
    sort(array,start,middle-1)
    sort(array,middle+1,end)
}

private fun getMiddle(array: Array<Int>, start: Int, end: Int) :Int{
    val pivot = array[start]
    var left = start
    var right = end
    while (left != right) {
        while (right > left && array[right] > pivot) {
            right--
        }
        while (right > left && array[left] <= pivot) {
            left++
        }
        if (left<right){
            val temp = array[left]
            array[left] = array[right]
            array[right] = temp
        }
    }
    array[start] = array[left]
    array[left] = pivot
    return right
}